package com.huawei.tree;

import com.huawei.common.TreeNode;

/**
 * @Author admin
 * @Description 恢复二叉搜索树 https://leetcode.cn/problems/recover-binary-search-tree/
 * @Date 2023/11/16/22:07
 * @Version 1.0
 */
public class RecoverTree {
	TreeNode a = null, b = null, last = null;

	/**
	 * 解题思路： 所谓的恢复二叉树（两节点互换），只需要将两节点的 val 进行互换即可，而不需要对节点本身进行互换。
	 * 二叉搜索树，其中序遍历是有序的。 要找到哪两个节点被互换，可通过比对中序遍历序列来实现。
	 * 除了使用 a 和 b 来记录互换节点，额外使用变量 last 来记录当前遍历过程中的前一节点即可：
	 * 若存在前一节点 last 存在，而且满足前一节点值大于当前节点（last.val > root.val），违反“有序性”
	 * (1) 若是首次满足条件，即 a == null，此时上一节点 last 必然是两个互换节点之一，
	 *      而当前 root 只能说是待定，因为有可能是 last 和 root 实现互换，也有可能是 last 和后续的某个节点实现互换。 此时有 a = last, b = root
	 * (2) 若是非首次满足条件，即 a != null，此时当前节点 root 必然是两个互换节点中的另外一个。 此时有 b = root
	 * @param root TreeNode
	 */
	public void recoverTree(TreeNode root) {
		dfs(root);
		int val = a.val;
		a.val = b.val;
		b.val = val;
	}

	void dfs(TreeNode root) {
		if (root == null) {
			return;
		}
		dfs(root.left);
		if (last != null && last.val > root.val) {
			if (a == null) {
				a = last;
				b = root;
			} else {
				b = root;
			}
		}
		last = root;
		dfs(root.right);
	}


}
